/*
 *   This program is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   This program is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

/*
 * BallTreeConstructor.java
 * Copyright (C) 2007-2012 University of Waikato, Hamilton, New Zealand
 */

package weka.core.neighboursearch.balltrees;

import java.io.Serializable;
import java.util.Enumeration;
import java.util.Vector;

import weka.core.DistanceFunction;
import weka.core.EuclideanDistance;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.Utils;

/**
 * Abstract class for constructing a BallTree .
 * 
 * @author Ashraf M. Kibriya (amk14[at-the-rate]cs[dot]waikato[dot]ac[dot]nz)
 * @version $Revision$
 */
public abstract class BallTreeConstructor implements OptionHandler, Serializable {

    /** ID to avoid warning */
    private static final long serialVersionUID = 982315539809240771L;

    /** The maximum number of instances allowed in a leaf. */
    protected int m_MaxInstancesInLeaf = 40;

    /**
     * The maximum relative radius of a leaf node (relative to the smallest ball
     * enclosing all the data (training) points).
     */
    protected double m_MaxRelLeafRadius = 0.001;

    /**
     * Should a parent ball completely enclose the balls of its two children, or
     * only the points inside its children.
     */
    protected boolean m_FullyContainChildBalls = false;

    /** The instances on which to build the tree. */
    protected Instances m_Instances;

    /** The distance function to use to build the tree. */
    protected DistanceFunction m_DistanceFunction;

    /**
     * The number of internal and leaf nodes in the built tree.
     */
    protected int m_NumNodes;

    /** The number of leaf nodes in the built tree. */
    protected int m_NumLeaves;

    /** The depth of the built tree. */
    protected int m_MaxDepth;

    /** The master index array. */
    protected int[] m_InstList;

    /**
     * Creates a new instance of BallTreeConstructor.
     */
    public BallTreeConstructor() {
    }

    /**
     * Builds the ball tree.
     * 
     * @return The root node of the tree.
     * @throws Exception If there is problem building the tree.
     */
    public abstract BallNode buildTree() throws Exception;

    /**
     * Adds an instance to the ball tree.
     * 
     * @param node The root node of the tree.
     * @param inst The instance to add to the tree.
     * @return The new master index array after adding the instance.
     * @throws Exception If there is some problem adding the given instance to the
     *                   tree.
     */
    public abstract int[] addInstance(BallNode node, Instance inst) throws Exception;

    /**
     * Returns the tip text for this property.
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui.
     */
    public String maxInstancesInLeafTipText() {
        return "The maximum number of instances allowed in a leaf.";
    }

    /**
     * Returns the maximum number of instances allowed in a leaf.
     * 
     * @return The maximum number of instances allowed in a leaf.
     */
    public int getMaxInstancesInLeaf() {
        return m_MaxInstancesInLeaf;
    }

    /**
     * Sets the maximum number of instances allowed in a leaf.
     * 
     * @param num The maximum number of instances allowed in a leaf.
     * @throws Exception If the num is < 1.
     */
    public void setMaxInstancesInLeaf(int num) throws Exception {
        if (num < 1) {
            throw new Exception("The maximum number of instances in a leaf must " + "be >=1.");
        }
        m_MaxInstancesInLeaf = num;
    }

    /**
     * Returns the tip text for this property.
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui.
     */
    public String maxRelativeLeafRadiusTipText() {
        return "The maximum relative radius allowed for a leaf node. " + "Itis relative to the radius of the smallest ball " + "enclosing all the data points (that were used to " + "build the tree). This smallest ball would be the " + "same as the root node's ball, if ContainChildBalls " + "property is set to false (default).";
    }

    /**
     * Returns the maximum relative radius of a leaf node. It is relative to the
     * radius of the smallest ball enclosing all the data points (that were used to
     * build the tree). This smallest ball would be the same as the root node's
     * ball, if ContainChildBalls property is set to false (default).
     * 
     * @return The maximum relative radius allowed for a leaf.
     */
    public double getMaxRelativeLeafRadius() {
        return m_MaxRelLeafRadius;
    }

    /**
     * Sets the maximum relative radius, allowed for a leaf node. The radius is
     * relative to the radius of the smallest ball enclosing all the data points
     * (that were used to build the tree). This smallest ball would be the same as
     * the root node's ball, if ContainChildBalls property is set to false
     * (default).
     * 
     * @param radius The maximum relative radius allowed for a leaf.
     * @throws Exception If radius is < 0.0.
     */
    public void setMaxRelativeLeafRadius(double radius) throws Exception {
        if (radius < 0.0) {
            throw new Exception("The radius for the leaves should be >= 0.0");
        }
        m_MaxRelLeafRadius = radius;
    }

    /**
     * Returns the tip text for this property.
     * 
     * @return tip text for this property suitable for displaying in the
     *         explorer/experimenter gui.
     */
    public String containChildBallsTipText() {
        return "Whether to contain fully the child balls.";
    }

    /**
     * Gets whether if a parent ball should completely enclose its two child balls.
     * 
     * @return true if parent ball is to enclose its child balls.
     */
    public boolean getContainChildBalls() {
        return m_FullyContainChildBalls;
    }

    /**
     * Sets whether if a parent ball should completely enclose its two child balls.
     * 
     * @param containChildBalls Should be tree if parent ball is to enclose its
     *                          child balls.
     */
    public void setContainChildBalls(boolean containChildBalls) {
        m_FullyContainChildBalls = containChildBalls;
    }

    /**
     * Sets the instances on which the tree is to be built.
     * 
     * @param inst The instances on which to build the ball tree.
     */
    public void setInstances(Instances inst) {
        m_Instances = inst;
    }

    /**
     * Sets the master index array that points to instances in m_Instances, so that
     * only this array is manipulated, and m_Instances is left untouched.
     * 
     * @param instList The master index array.
     */
    public void setInstanceList(int[] instList) {
        m_InstList = instList;
    }

    /**
     * Sets the distance function to use to build the tree.
     * 
     * @param func The distance function.
     */
    public void setEuclideanDistanceFunction(EuclideanDistance func) {
        m_DistanceFunction = func;
    }

    /**
     * Returns the number of nodes (internal + leaf) in the built tree.
     * 
     * @return The number of nodes in the tree.
     */
    public int getNumNodes() {
        return m_NumNodes;
    }

    /**
     * Returns the number of leaves in the built tree.
     * 
     * @return The number of leaves in the tree.
     */
    public int getNumLeaves() {
        return m_NumLeaves;
    }

    /**
     * Returns the depth of the built tree.
     * 
     * @return The depth of the tree.
     */
    public int getMaxDepth() {
        return m_MaxDepth;
    }

    /**
     * Returns an enumeration describing the available options.
     * 
     * @return an enumeration of all the available options.
     */
    @Override
    public Enumeration<Option> listOptions() {
        Vector<Option> newVector = new Vector<Option>();

        newVector.addElement(new Option("\tSet maximum number of instances in a leaf node\n" + "\t(default: 40)", "N", 0, "-N <value>"));

        newVector.addElement(new Option("\tSet internal nodes' radius to the sum \n" + "\tof the child balls radii. So that it \n" + "contains the child balls.", "R", 0, "-R"));

        return newVector.elements();
    }

    /**
     * Parses a given list of options.
     * 
     * @param options the list of options as an array of strings
     * @throws Exception if an option is not supported
     */
    @Override
    public void setOptions(String[] options) throws Exception {

        String optionString = Utils.getOption('N', options);
        if (optionString.length() != 0) {
            setMaxInstancesInLeaf(Integer.parseInt(optionString));
        } else {
            setMaxInstancesInLeaf(40);
        }

        setContainChildBalls(Utils.getFlag('R', options));
    }

    /**
     * Gets the current settings.
     * 
     * @return an array of strings suitable for passing to setOptions
     */
    @Override
    public String[] getOptions() {
        Vector<String> result = new Vector<String>();

        result.add("-N");
        result.add("" + getMaxInstancesInLeaf());

        if (getContainChildBalls()) {
            result.add("-R");
        }

        return result.toArray(new String[result.size()]);
    }

}
